package com.wc.blue_bridge_history.Java12Q.D_覆盖;

import java.io.PrintWriter;

/**
 * @Author congge
 * @Date 2024/5/20 20:01
 * @description https://www.lanqiao.cn/problems/1564/learning/
 */
public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 9, M = 1 << N;
    static long[][] f = new long[N][M];
    static boolean[] st = new boolean[M];
    static int[] state = new int[M];
    static int len = 0;

    public static void main(String[] args) {
        int n = 8;
        for (int i = 0; i < 1 << n; i++) {
            int cnt = 0;
            boolean flg = true;
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    if ((cnt & 1) == 1) {
                        flg = false;
                        break;
                    }
                    cnt = 0;
                } else cnt++;
            }
            if ((cnt & 1) == 1) flg = false;
            if (flg) state[++len] = i;
            st[i] = flg;
        }
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 1 << n; j++) {
                for (int k = 0; k < 1 << n; k++) {
                    if ((j & k) == 0 && st[j | k]) {
                        f[i][j] += f[i - 1][k];
                    }
                }
            }
        }
//        System.out.println(len);
        out.println(f[n][0]);
        out.flush();
    }
}

